// This file is part of the Luau programming language and is licensed under MIT License; see LICENSE.txt for details
/*
MIT License

Copyright (c) 2019-2024 Roblox Corporation
Copyright (c) 1994-2019 Lua.org, PUC-Rio.

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

#pragma once

#include <algorithm>
#include <limits>
#include <memory>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>

namespace moon
{
// `VecDeque` is a general double-ended implementation designed as a drop-in replacement for the
// standard library `std::deque`. It's backed by a growable ring buffer, rather than using the
// segmented queue design of `std::deque` which can degrade into a linked list in the worst case.
// The motivation for `VecDeque` as a replacement is to maintain the asymptotic complexity of
// `std::deque` while reducing overall allocations and promoting better usage of the cache. Its API
// is intended to be compatible with `std::deque` and `std::vector` as appropriate, and as such
// provides corresponding method definitions and supports the use of custom allocators.
//
// `VecDeque` offers pushing and popping from both ends with an amortized O(1) complexity. It also
// supports `std::vector`-style random-access in O(1). The implementation of buffer resizing uses
// a growth factor of 1.5x to enable better memory reuse after resizing, and reduce overall memory
// fragmentation when using the queue.
//
// Since `VecDeque` is a ring buffer, its elements are not necessarily contiguous in memory. To
// describe this, we refer to the two portions of the buffer as the `head` and the `tail`. The
// `head` is the initial portion of the queue that is on the range `[head, capacity)` and the tail
// is the (optionally) remaining portion on the range `[0, head + size - capacity)` whenever the
// `head + size` exceeds the capacity of the buffer.
//
// `VecDeque` does not currently support iteration since its primary focus is on providing
// double-ended queue functionality specifically, but it can be reasonably expanded to provide
// an iterator if we have a use-case for one in the future.
template<typename T, class Allocator = std::allocator<T>>
class VecDeque : private Allocator
{
private:
    static_assert(std::is_nothrow_move_constructible_v<T>);
    static_assert(std::is_nothrow_move_assignable_v<T>);

    T* buffer = nullptr;        // the existing allocation we have backing this queue
    size_t buffer_capacity = 0; // the size of our allocation

    size_t head = 0;       // the index of the head of the queue
    size_t queue_size = 0; // the size of the queue

    void destroyElements() noexcept
    {
        if constexpr(!std::is_trivial_v<std::decay_t<T>>){
            size_t head_size =
            std::min(queue_size, capacity() - head); // how many elements are in the head portion (i.e. from the head to the end of the buffer)
            size_t tail_size = queue_size - head_size;   // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

            // we have to destroy every element in the head portion
            for (size_t index = head; index < head + head_size; index++)
                std::destroy_at(&buffer[index]);

            // and any in the tail portion, if one exists
            for (size_t index = 0; index < tail_size; index++)
                std::destroy_at(&buffer[index]);
        }
    }

    bool is_full()
    {
        return queue_size == capacity();
    }

    void grow()
    {
        size_t old_capacity = capacity();

        // we use a growth factor of 1.5x (plus a constant) here in order to enable the
        // previous memory to be reused after a certain number of calls to grow.
        // see: https://github.com/facebook/folly/blob/main/folly/docs/FBVector.md#memory-handling
        size_t new_capacity = (old_capacity > 0) ? old_capacity * 3 / 2 + 1 : 4;

        // check that it's a legal allocation
        if (new_capacity > max_size())
            throw std::bad_array_new_length();

        // allocate a new backing buffer
        T* new_buffer = this->allocate(new_capacity);

        // we should not be growing if the capacity is not the current size
        assert(old_capacity == queue_size);

        size_t head_size =
            std::min(queue_size, old_capacity - head); // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = queue_size - head_size;     // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        // move the head into the new buffer
        if (head_size != 0)
            std::uninitialized_move(buffer + head, buffer + head + head_size, new_buffer);

        // move the tail into the new buffer immediately after
        if (tail_size != 0)
            std::uninitialized_move(buffer, buffer + tail_size, new_buffer + head_size);

        // destroy the old elements
        destroyElements();
        // deallocate the old buffer
        this->deallocate(buffer, old_capacity);

        // set up the queue to be backed by the new buffer
        buffer = new_buffer;
        buffer_capacity = new_capacity;
        head = 0;
    }

    size_t logicalToPhysical(size_t pos)
    {
        return (head + pos) % capacity();
    }

public:
    VecDeque() = default;

    explicit VecDeque(const Allocator& alloc) noexcept
        : Allocator{alloc}
    {
    }

    VecDeque(const VecDeque& other)
        : buffer(this->allocate(other.buffer_capacity))
        , buffer_capacity(other.buffer_capacity)
        , head(other.head)
        , queue_size(other.queue_size)
    {
        // copy the initialized contents of the other buffer to this one
        size_t head_size = std::min(other.queue_size,
            other.buffer_capacity - other.head);         // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = other.queue_size - head_size; // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        if (head_size != 0)
            std::uninitialized_copy(other.buffer + other.head, other.buffer + other.head + head_size, buffer + head);

        if (tail_size != 0)
            std::uninitialized_copy(other.buffer, other.buffer + tail_size, buffer);
    }

    VecDeque(const VecDeque& other, const Allocator& alloc)
        : Allocator{alloc}
        , buffer(this->allocate(other.buffer_capacity))
        , buffer_capacity(other.buffer_capacity)
        , head(other.head)
        , queue_size(other.queue_size)
    {
        // copy the initialized contents of the other buffer to this one
        size_t head_size = std::min(other.queue_size,
            other.buffer_capacity - other.head);         // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = other.queue_size - head_size; // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        if (head_size != 0)
            std::uninitialized_copy(other.buffer + other.head, other.buffer + other.head + head_size, buffer + head);

        if (tail_size != 0)
            std::uninitialized_copy(other.buffer, other.buffer + tail_size, buffer);
    }

    VecDeque(VecDeque&& other) noexcept
        : buffer(std::exchange(other.buffer, nullptr))
        , buffer_capacity(std::exchange(other.buffer_capacity, 0))
        , head(std::exchange(other.head, 0))
        , queue_size(std::exchange(other.queue_size, 0))
    {
    }

    VecDeque(VecDeque&& other, const Allocator& alloc) noexcept
        : Allocator{alloc}
        , buffer(std::exchange(other.buffer, nullptr))
        , buffer_capacity(std::exchange(other.buffer_capacity, 0))
        , head(std::exchange(other.head, 0))
        , queue_size(std::exchange(other.queue_size, 0))
    {
    }

    VecDeque(std::initializer_list<T> init, const Allocator& alloc = Allocator())
        : Allocator{alloc}
    {
        buffer = this->allocate(init.size());
        buffer_capacity = init.size();
        queue_size = init.size();

        std::uninitialized_copy(init.begin(), init.end(), buffer);
    }

    ~VecDeque() noexcept
    {
        // destroy any elements that exist
        destroyElements();
        // free the allocated buffer
        this->deallocate(buffer, buffer_capacity);
    }

    VecDeque& operator=(const VecDeque& other)
    {
        if (this == &other)
            return *this;

        // destroy all of the existing elements
        destroyElements();

        if (buffer_capacity < other.size())
        {
            // free the current buffer
            this->deallocate(buffer, buffer_capacity);

            buffer = this->allocate(other.buffer_capacity);
            buffer_capacity = other.buffer_capacity;
        }

        size_t head_size = std::min(other.queue_size,
            other.buffer_capacity - other.head);         // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = other.queue_size - head_size; // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        // Assignment doesn't try to match the capacity of 'other' and thus makes the buffer contiguous
        head = 0;
        queue_size = other.queue_size;

        if (head_size != 0)
            std::uninitialized_copy(other.buffer + other.head, other.buffer + other.head + head_size, buffer);

        if (tail_size != 0)
            std::uninitialized_copy(other.buffer, other.buffer + tail_size, buffer + head_size);

        return *this;
    }

    VecDeque& operator=(VecDeque&& other)
    {
        if (this == &other)
            return *this;

        // destroy all of the existing elements
        destroyElements();
        // free the current buffer
        this->deallocate(buffer, buffer_capacity);

        buffer = std::exchange(other.buffer, nullptr);
        buffer_capacity = std::exchange(other.buffer_capacity, 0);
        head = std::exchange(other.head, 0);
        queue_size = std::exchange(other.queue_size, 0);

        return *this;
    }

    Allocator get_allocator() const noexcept
    {
        return this;
    }

    // element access

    T& at(size_t pos)
    {
        if (pos >= queue_size)
            throw std::out_of_range("VecDeque");

        return buffer[logicalToPhysical(pos)];
    }

    const T& at(size_t pos) const
    {
        if (pos >= queue_size)
            throw std::out_of_range("VecDeque");

        return buffer[logicalToPhysical(pos)];
    }

    [[nodiscard]] T& operator[](size_t pos) noexcept
    {
        assert(pos < queue_size);

        return buffer[logicalToPhysical(pos)];
    }

    [[nodiscard]] const T& operator[](size_t pos) const noexcept
    {
        assert(pos < queue_size);

        return buffer[logicalToPhysical(pos)];
    }

    T& front()
    {
        LUAU_ASSERT(!empty());

        return buffer[head];
    }

    const T& front() const
    {
        LUAU_ASSERT(!empty());

        return buffer[head];
    }

    T& back()
    {
        LUAU_ASSERT(!empty());

        size_t back = logicalToPhysical(queue_size - 1);
        return buffer[back];
    }

    const T& back() const
    {
        LUAU_ASSERT(!empty());

        size_t back = logicalToPhysical(queue_size - 1);
        return buffer[back];
    }

    // capacity

    bool empty() const noexcept
    {
        return queue_size == 0;
    }

    size_t size() const noexcept
    {
        return queue_size;
    }

    size_t max_size() const noexcept
    {
        return std::numeric_limits<size_t>::max() / sizeof(T);
    }

    void reserve(size_t new_capacity)
    {
        // error if this allocation would be illegal
        if (new_capacity > max_size())
            throw std::length_error("too large");

        size_t old_capacity = capacity();

        // do nothing if we're requesting a capacity that would not cause growth
        if (new_capacity <= old_capacity)
            return;

        size_t head_size =
            std::min(queue_size, old_capacity - head); // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = queue_size - head_size;     // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        // allocate a new backing buffer
        T* new_buffer = this->allocate(new_capacity);

        // move the head into the new buffer
        if (head_size != 0)
            std::uninitialized_move(buffer + head, buffer + head + head_size, new_buffer);

        // move the tail into the new buffer immediately after
        if (tail_size != 0)
            std::uninitialized_move(buffer, buffer + tail_size, new_buffer + head_size);

        // destroy all the existing elements before freeing the old buffer
        destroyElements();

        // deallocate the old buffer
        this->deallocate(buffer, old_capacity);

        // set up the queue to be backed by the new buffer
        buffer = new_buffer;
        buffer_capacity = new_capacity;
        head = 0;
    }

    size_t capacity() const noexcept
    {
        return buffer_capacity;
    }

    void shrink_to_fit()
    {
        size_t old_capacity = capacity();
        size_t new_capacity = queue_size;

        if (old_capacity == new_capacity)
            return;

        size_t head_size =
            std::min(queue_size, old_capacity - head); // how many elements are in the head portion (i.e. from the head to the end of the buffer)
        size_t tail_size = queue_size - head_size;     // how many elements are in the tail portion (i.e. any portion that wrapped to the front)

        // allocate a new backing buffer
        T* new_buffer = this->allocate(new_capacity);

        // move the head into the new buffer
        if (head_size != 0)
            std::uninitialized_move(buffer + head, buffer + head + head_size, new_buffer);

        // move the tail into the new buffer immediately after, if we have one
        if (tail_size != 0)
            std::uninitialized_move(buffer, buffer + tail_size, new_buffer + head_size);

        // destroy all the existing elements before freeing the old buffer
        destroyElements();
        // deallocate the old buffer
        this->deallocate(buffer, old_capacity);

        // set up the queue to be backed by the new buffer
        buffer = new_buffer;
        buffer_capacity = new_capacity;
        head = 0;
    }

    [[nodiscard]] bool is_contiguous() const noexcept
    {
        // this is an overflow-safe alternative to writing `head + size <= capacity`.
        return head <= capacity() - queue_size;
    }

    // modifiers

    void clear() noexcept
    {
        destroyElements();

        head = 0;
        queue_size = 0;
    }

    void push_back(const T& value)
    {
        if (is_full())
            grow();

        size_t next_back = logicalToPhysical(queue_size);
        new (buffer + next_back) T(value);
        queue_size++;
    }

    template<typename ...Args>
    void emplace_back(Args&&...arg)
    {
        if (is_full())
            grow();


        size_t next_back = logicalToPhysical(queue_size);
        new (buffer + next_back) T{std::forward<Args>(arg)...};
        queue_size++;
    }   

    void pop_back()
    {
        LUAU_ASSERT(!empty());

        queue_size--;
        size_t next_back = logicalToPhysical(queue_size);
        buffer[next_back].~T();
    }

    void push_front(const T& value)
    {
        if (is_full())
            grow();

        head = (head == 0) ? capacity() - 1 : head - 1;
        new (buffer + head) T(value);
        queue_size++;
    }

    void pop_front()
    {
        assert(!empty());

        buffer[head].~T();
        head++;
        queue_size--;

        if (head == capacity())
            head = 0;
    }
};

} // namespace moon